04. 系统原理

1. 数据库管理系统（DBMS）架构

1.1 DBMS核心组件 (The Components of DBMS Core)

DBMS核心是数据库系统的中枢，负责处理用户请求、管理数据存储和确保数据一致性。其主要组件协同工作，将高级的数据库语句（如SQL）转化为对底层存储的实际操作。

语义分析与查询处理 (Semantic Analysis and Query Treatment)：
- DDL (Data Definition Language)：数据定义语言，用于定义数据库结构，如创建表、索引等。
- QL (Query Language)：查询语言，用于查询数据，如SELECT语句。
- DML (Data Manipulation Language)：数据操作语言，用于修改数据，如INSERT、UPDATE、DELETE。
- DCL (Data Control Language)：数据控制语言，用于权限管理和事务控制，如GRANT、REVOKE。
- 解析器 (Parser)：将SQL语句解析成内部表示形式，通常是语法树 (Grammar Tree)。
- 授权检查 (Grant Checking)：验证用户是否有执行操作的权限。
并发控制 (Concurrency Control)：管理多个并发事务对数据库的访问，确保数据的一致性和隔离性。
恢复机制 (Recovery Mechanism)：在系统故障（如断电、软件崩溃）后，将数据库恢复到一致状态。
访问管理 (Access Management)：负责数据的物理存储和检索，将逻辑数据请求转化为对操作系统文件或裸设备的I/O操作。

1.2 DBMS进程结构 (The Process Structure of DBMS)

DBMS的进程结构决定了其如何处理来自应用程序的并发请求。

单进程结构 (Single Process Structure)：
- 应用程序代码与DBMS核心编译成一个独立的 .exe 文件，作为一个单一进程运行。
- 优点：结构简单，开销小。
- 缺点：无法支持多用户并发访问，扩展性差，通常用于嵌入式或小型数据库。
- 用例：SQLite数据库，常用于移动应用或桌面应用，其数据库引擎直接嵌入到应用程序中。
多进程结构 (Multi Processes Structure)：
- 每个应用程序进程对应一个独立的DBMS核心进程。
- 应用程序进程通过进程间通信（如管道pipe）与DBMS核心进程交互。
- 优点：进程间隔离性好，一个DBMS核心进程崩溃不会影响其他进程。
- 缺点：进程创建和切换开销大，资源消耗高。
- 用例：早期的数据库系统，如Oracle的专用服务器模式（Dedicated Server Mode），每个客户端连接都会启动一个独立的服务器进程。
多线程结构 (Multi Threads Structure)：
- 只有一个DBMS主进程（通常称为守护进程DAEMON），每个应用程序进程通过管道/套接字与DBMS主进程通信。
- DBMS主进程为每个应用程序请求创建一个或分配一个DBMS核心线程来处理。
- 所有线程共享DBMS主进程的资源（如目录、锁表、缓冲区）。
- 优点：线程创建和切换开销小于进程，资源共享效率高，并发性好。
- 缺点：线程间共享内存，一个线程的错误可能影响整个DBMS进程。
- 用例：现代主流数据库系统（如MySQL、PostgreSQL、SQL Server、Oracle的共享服务器模式），通常采用多线程或混合（多进程+多线程）结构来提高并发处理能力。

2. 数据库访问管理 (Database Access Management)

数据库访问管理是将逻辑数据请求转化为对操作系统文件或裸设备的物理I/O操作的关键环节。文件结构和访问路径的选择直接影响数据访问速度。

2.1 访问类型 (Access Types)

不同的查询类型需要不同的访问策略。

查询文件中的全部或大部分记录（>15%）。
查询特定记录（精确匹配）。
查询部分记录（<15%）。
范围查询 (Scope Query)。
更新操作 (Update)。

2.2 文件组织 (File Organization)

文件组织方式决定了数据在磁盘上的物理存储布局。

堆文件 (Heap File)：
- 记录按插入顺序存储，检索时顺序扫描。
- 特点：最基本和通用的文件组织形式。
- 适用场景：适合批量插入，不适合频繁查询特定记录。
直接文件 (Direct File)：
- 记录地址通过哈希函数根据某个属性值映射。
- 特点：通过哈希函数直接定位记录，访问速度快。
- 适用场景：适合精确匹配查询。
索引文件 (Indexed File)：
- 结合索引和堆文件/聚簇文件。
- 特点：通过索引快速定位记录，提高查询效率。
动态哈希 (Dynamic Hashing)：
- 一种支持动态扩展和收缩的哈希技术。
- 特点：解决了静态哈希表大小固定、冲突处理复杂的问题。
网格结构文件 (Grid Structure File)：
- 适用于多属性查询。
- 特点：将多维数据空间划分为网格，支持多维范围查询。
裸设备 (Raw Disk)：
- 直接访问磁盘的物理块，绕过操作系统的文件系统缓存。
- 特点：DBMS可以更精细地控制物理I/O，提高性能，但管理复杂。
- 注意：逻辑块与物理块的区别。

2.3 索引技术 (Index Technique)

索引是提高数据检索效率的关键。

B+树 (B+ Tree)：
- 特点：广泛应用于数据库和文件系统，支持高效的范围查询和精确匹配查询，所有叶子节点通过指针连接，便于范围遍历。
- 重要性：非常重要，几乎所有关系型数据库都使用B+树作为主要索引结构。
聚簇索引 (Clustering Index)：
- 特点：数据行的物理存储顺序与索引的逻辑顺序一致，一个表只能有一个聚簇索引。
- 优点：对于范围查询和按索引列排序的查询性能极佳，因为相关数据物理上是连续的。
- 缺点：插入和更新可能导致数据重组。
倒排文件 (Inverted File)：
- 特点：记录某个属性值出现在哪些记录中，常用于全文检索。
位图索引 (Bitmap Index)：
- 特点：适用于低基数（distinct值少）的列，通过位图表示数据存在性。
- 适用场景：数据仓库和OLAP（联机分析处理）系统。

3. 查询优化 (Query Optimization)

查询优化的目标是以最低的成本和最短的时间获取用户查询结果。它通过“重写”用户提交的查询语句，并选择最有效的操作方法和步骤来实现。

3.1 查询优化概述 (Summary of Query Optimization)

查询优化分为两个主要阶段：

代数优化 (Algebra Optimization)：
- 对原始查询表达式进行一系列等价转换，将其转换为等价但更有效的执行形式。
- 核心思想：尽早过滤数据，减少中间结果集。
- 用例：将选择（ $\sigma$ $σ$ ）操作下推到连接（ $\bowtie$ $⋈$ ）操作之前，可以显著减少参与连接的数据量。
  - 例如： $\Pi_{S.SNAME}(\sigma_{S.CITY='Nanjing' \land P.PNAME='Bolt' \land SP.QUAN>1000}(S \bowtie_{S.SNUM=SP.SNUM} SP \bowtie_{SP.PNUM=P.PNUM} P))$
  - 经过代数优化后，可以先对S、SP、P表进行选择操作，再进行连接，减少中间结果集的大小。
操作优化 (Operation Optimization)：
- 决定如何具体执行代数优化后的查询计划，包括选择具体的算法（如连接算法）、访问路径（是否使用索引）等。
- 核心思想：选择成本最低的物理执行计划。

3.2 查询的等价转换 (The Equivalent Transform of a Query)

等价转换基于关系代数规则，将查询树转换为更优的执行顺序。

查询树 (Query Tree)：
- 叶子节点：关系（表）。
- 中间节点：一元/二元操作（如选择、投影、连接）。
- 从叶子到根的顺序：操作的执行顺序。
关系代数等价转换规则 (The equivalent transform rules of relational algebra)：
- 交换律： $\underline{E_1 \times E_2 \equiv E_2 \times E_1}$ （笛卡尔积/连接）
- 结合律： $\underline{E_1 \times (E_2 \times E_3) \equiv (E_1 \times E_2) \times E_3}$
- 投影的簇集规则： $\Pi_{A_1...A_n}(\Pi_{B_1...B_m}(E)) \equiv \Pi_{A_1...A_n}(E)$ ，当 $\{A_1...A_n\} \subseteq \{B_1...B_m\}$ 时合法。
- 选择的簇集规则： $\sigma_{F_1}(\sigma_{F_2}(E)) \equiv \sigma_{F_1 \land F_2}(E)$
- 选择与投影的交换规则： $\sigma_F(\Pi_{A_1...A_n}(E)) \equiv \Pi_{A_1...A_n}(\sigma_F(E))$ $σ_{F} (Π_{A_{1} ... A_{n}} (E)) \equiv Π_{A_{1} ... A_{n}} (σ_{F} (E))$ 。
  - 如果 $F$ 包含不属于 $\{A_1...A_n\}$ 的属性 $\{B_1...B_m\}$ ，则 $\Pi_{A_1...A_n}(\sigma_F(E)) \equiv \Pi_{A_1...A_n}(\sigma_F(\Pi_{A_1...A_n, B_1...B_m}(E)))$ 。
- 选择与笛卡尔积的交换规则：
  - 如果 $F$ 只包含 $E_1$ 的属性： $\sigma_F(E_1 \times E_2) \equiv \sigma_F(E_1) \times E_2$ 。
  - 如果 $F = F_1 \land F_2$ ，且 $F_1$ 只包含 $E_1$ 的属性， $F_2$ 只包含 $E_2$ 的属性： $\sigma_F(E_1 \times E_2) \equiv \sigma_{F_1}(E_1) \times \sigma_{F_2}(E_2)$ 。
  - 如果 $F = F_1 \land F_2$ ，且 $F_1$ 只包含 $E_1$ 的属性， $F_2$ 包含 $E_1$ 和 $E_2$ 的属性： $\sigma_F(E_1 \times E_2) \equiv \sigma_{F_2}(\sigma_{F_1}(E_1) \times E_2)$ 。
- 选择与并/差集的分配律：
  - $\sigma_F(E_1 \cup E_2) \equiv \sigma_F(E_1) \cup \sigma_F(E_2)$
  - $\sigma_F(E_1 - E_2) \equiv \sigma_F(E_1) - \sigma_F(E_2)$
- 投影与笛卡尔积的分配律：
  - $\Pi_{A_1...A_n}(E_1 \times E_2) \equiv \Pi_{B_1...B_m}(E_1) \times \Pi_{C_1...C_k}(E_2)$ ，其中 $\{B_1...B_m\}$ 是 $E_1$ 的属性， $\{C_1...C_k\}$ 是 $E_2$ 的属性，且 $\{A_1...A_n\} = \{B_1...B_m\} \cup \{C_1...C_k\}$ 。
- 投影与并集的分配律： $\Pi_{A_1...A_n}(E_1 \cup E_2) \equiv \Pi_{A_1...A_n}(E_1) \cup \Pi_{A_1...A_n}(E_2)$ 。
基本原则 (Basic principles)：
- 尽可能将一元操作下推：将选择（ $\sigma$ ）和投影（ $\Pi$ ）操作尽可能下推到查询树的叶子节点，以减少中间结果集的大小。
- 查找并合并公共子表达式 (Look for and combine the common sub-expression)：避免重复计算。

3.3 操作优化 (The Operation Optimization)

操作优化关注如何选择具体的算法来执行查询操作。

连接操作优化 (Optimization of join operation)：
- 嵌套循环连接 (Nested Loop Join)：
  - 一个关系作为外层循环（O），另一个作为内层循环（I）。对于O中的每条元组，扫描I一次以检查连接条件。
  - 成本计算：对于 $R \bowtie S$ ，如果 $R$ 作为外层， $S$ 作为内层， $b_R$ 是 $R$ 的物理块数， $b_S$ 是 $S$ 的物理块数，系统有 $n_B$ 个块缓冲区（ $n_B \ge 2$ ），其中 $n_B-1$ 个用于 $O$ ，一个用于 $I$ ，则总磁盘访问次数为： $b_R + \lceil b_R / (n_B - 1) \rceil \times b_S$
  - 特点：最通用的连接算法，适用于各种情况，但效率可能较低。
- 归并排序连接 (Merge Scan Join)：
  - 要求参与连接的关系预先在连接属性上排序。如果未排序，需要考虑排序成本。
  - 特点：如果数据已排序，只需对两个关系各扫描一次，效率高。
- 使用索引或哈希查找匹配元组 (Using index or hash to look for mapping tuples)：
  - 在嵌套循环连接中，如果内层关系在连接属性上有合适的索引（如B+树索引），可以替代顺序扫描，显著提高效率。
  - 特点：当连接属性上有聚簇索引或哈希时效果最佳。
- 哈希连接 (Hash Join)：
  - 将两个关系根据连接属性使用相同的哈希函数散列到哈希文件中，然后在哈希文件上进行连接。
  - 特点：对于大数据集和等值连接效率很高。

4. 恢复 (Recovery)

恢复机制的主要作用是减少故障发生的可能性（预防）和从故障中恢复（解决），将数据库恢复到一致状态。

4.1 恢复简介 (Introduction)

冗余 (Redundancy)：是实现恢复的必要条件，通过备份、日志等方式存储冗余信息。
通用方法：
- 周期性转储 (Periodical Dumping)：
  - 特点：简单易实现，开销低。
  - 缺点：故障发生后，转储点到故障点之间的更新可能丢失。
  - 变种：备份 + 增量转储 (Incremental Dumping)（只备份更新的部分）。
  - 适用场景：文件系统或小型DBMS。
- 备份 + 日志 (Backup + Log)：
  - 日志 (Log)：记录自上次备份以来数据库的所有更改。
  - 记录内容：
    - 更新操作：旧值 (Before Image - B.I) 和新值 (After Image - A.I)。
    - 插入操作：新值 (A.I)。
    - 删除操作：旧值 (B.I)。
  - 恢复过程：
    - Undo (撤销)：对于未完成的事务，使用日志中的B.I撤销其修改。
    - Redo (重做)：对于已完成但结果未及时写入数据库的事务，使用日志中的A.I重做其修改。
  - 特点：可以恢复数据库到最近的一致状态。

4.2 事务 (Transaction)

事务是数据库管理系统执行的逻辑工作单元，具有ACID特性。

原子性 (Atomicity)：事务是不可分割的最小工作单元，要么全部完成，要么全部不完成（Nothing or All）。
- Rollback (回滚)：异常终止，撤销所有操作。
- Commit (提交)：正常终止，永久保存所有操作。
一致性 (Consistency Preservation)：事务执行前后，数据库从一个一致状态转换到另一个一致状态。
隔离性 (Isolation)：并发事务的执行互不影响，如同串行执行一样。
持久性 (Durability)：一旦事务成功完成（提交），其对数据库的修改是永久的，即使系统发生故障也能恢复。

用例：转账操作

Begin transaction
read A
A := A - s
if A < 0 then
    Display "insufficient fund"
    Rollback /* 撤销并终止 */
else
    B := B + s
    Display "transfer complete"
    Commit /* 提交更新并终止 */

4.3 支持恢复的结构 (Some Structures to Support Recovery)

恢复信息（如日志）必须存储在**非易失性存储器 (nonvolatile storage)**中。

提交列表 (Commit List)：已提交事务的事务ID (TID) 列表。
活动列表 (Active List)：正在进行中事务的TID列表。
日志 (Log)：记录事务ID、数据块ID、旧值、新值等信息。

4.4 提交规则和日志先行规则 (Commit Rule and Log Ahead Rule)

这些规则确保在故障发生时能够正确恢复。

提交规则 (Commit Rule)：事务提交前，所有新值 (A.I) 必须写入非易失性存储器（通常是日志）。
日志先行规则 (Log Ahead Rule)：如果新值 (A.I) 在事务提交前写入数据库，则旧值 (B.I) 必须首先写入日志。

Undo和Redo的特性：它们是**幂等 (idempotent)**的，即多次执行效果与一次执行相同。
- $undo(undo(...undo(x)...)) = undo(x)$
- $redo(redo(...redo(x)...)) = redo(x)$

三种更新策略下的恢复 (Three kinds of update strategy)：

策略	A.I写入DB时机	日志记录	恢复时对已提交事务	恢复时对未提交事务
a)	提交前	B.I（日志先行）	无需操作	Undo
b)	提交后	A.I（提交规则）	Redo	无需操作
c)	与提交并发	A.I, B.I（两规则）	Redo	Undo

策略a)：A.I在事务提交前写入DB。恢复时，已提交事务的数据已在DB中，无需Redo；未提交事务的数据可能已写入DB，需要Undo。
策略b)：A.I在事务提交后才写入DB。恢复时，已提交事务的数据可能未写入DB，需要Redo；未提交事务的数据未写入DB，无需Undo。
策略c)：A.I在事务提交过程中写入DB。恢复时，已提交事务可能部分写入DB，需要Redo确保完整性；未提交事务可能部分写入DB，需要Undo。

5. 并发控制 (Concurrency Control)

在多用户DBMS中，允许并发事务访问数据库，以提高系统利用率和响应时间。

5.1 并发控制简介 (Introduction)

为何需要并发？
1. 提高系统利用率和响应时间。
2. 不同事务可能访问数据库的不同部分。
并发执行带来的问题：
- 丢失更新 (Lost Update)：一个事务的更新被另一个事务的更新覆盖。
  - T1读取x，T2读取x，T1更新x，T2更新x，T1的更新丢失。
- 脏读 (Dirty Read)：一个事务读取了另一个未提交事务的数据，而该未提交事务最终回滚。
  - T1写入x，T2读取x，T1回滚，T2读取的是脏数据。
- 不可重复读 (Unrepeatable Read)：一个事务两次读取同一数据，但两次读取之间有另一个事务修改了该数据。
  - T1第一次读取x，T2修改x并提交，T1第二次读取x，两次结果不同。
- 写-写冲突 (Write-Write Conflict)：两个事务同时修改同一数据。必须避免。
- 写-读冲突 (Write-Read Conflict)：一个事务写入数据，另一个事务读取该数据。
- 读-写冲突 (Read-Write Conflict)：一个事务读取数据，另一个事务写入该数据。
- 注意：写-读和读-写冲突通常需要避免，但在某些应用中可以容忍。

5.2 可串行化 (Serialization)

定义：假设 $\{T_1, T_2, ..., T_n\}$ 是一组并发执行的事务。如果一个调度对数据库产生的影响与这组事务的某个串行执行序列产生的影响相同，则称该调度是**可串行化 (Serializable)**的。

问题：不同的调度可能导致不同的等价串行执行序列，从而产生不同的结果。
目标：找到一个调度，使其等价于某个串行执行，从而保证数据一致性。

5.3 封锁协议 (Locking Protocol)

封锁方法是最基本的并发控制方法。

1. 排他锁 (X locks)：
- 只有一种锁类型，用于读写操作。
- 兼容矩阵：
  
  NL X
  NL Y Y
  X Y N
  - NL (No Lock)：无锁。
  - Y (Compatible)：兼容。
  - N (Incompatible)：不兼容。
- 特点：简单，但并发度低。
2. 两阶段封锁协议 (Two Phase Locking - 2PL)：
- 定义1：在一个事务中，如果所有加锁操作都先于所有解锁操作，则称该事务为两阶段事务。此限制称为两阶段封锁协议。
  - 增长阶段 (Growing Phase)：事务只能加锁，不能解锁。
  - 收缩阶段 (Shrinking Phase)：事务只能解锁，不能加锁。
- 定义2：如果事务在操作对象前先对其加锁，则称其为良好形式 (Well-formed)。
- 定理：如果调度 $S$ 是良好形式且两阶段事务的调度，则 $S$ 是可串行化的。
- 结论：
  1. 良好形式 + 2PL：可串行化。
  2. 良好形式 + 2PL + 在事务结束时解锁更新：可串行化且可恢复 (Recoverable)（无级联回滚）。
  3. 良好形式 + 2PL + 持有所有锁直到事务结束：**严格两阶段封锁 (Strict Two Phase Locking)**事务。
3. 共享锁 (S locks) 和排他锁 (X locks)：
- S锁 (S lock)：用于读访问。
- X锁 (X lock)：用于写访问。
- 兼容矩阵：
  
  NL S X
  NL Y Y Y
  S Y Y N
  X Y N N
- 特点：提高了并发度，允许多个事务同时读取数据。
4. 共享锁 (S locks)、更新锁 (U locks) 和排他锁 (X locks)：
- U锁 (U lock)：更新锁。事务在更新前首先获取U锁，然后将其提升为X锁。
- 兼容矩阵：
  
  NL S U X
  NL Y Y Y Y
  S Y Y Y N
  U Y Y N N
  X Y N N N
- 目的：缩短排他时间，提高并发度，减少死锁。

	NL	X
NL	Y	Y
X	Y	N

	NL	S	X
NL	Y	Y	Y
S	Y	Y	N
X	Y	N	N

	NL	S	U	X
NL	Y	Y	Y	Y
S	Y	Y	Y	N
U	Y	Y	N	N
X	Y	N	N	N

5.4 死锁与活锁 (Deadlock & Live Lock)

死锁 (Deadlock)：事务之间形成循环等待，没有事务可以获得完成所需的所有资源。
- 用例：T1持有R1请求R2，T2持有R2请求R1。
活锁 (Live Lock)：尽管其他事务在有限时间内释放了资源，但某些事务长时间无法获得所需资源。
- 用例：T1、T2、T3都请求R，T1和T2轮流获得R，T3一直无法获得。
- 解决：调整调度策略，如FIFO（先进先出）。
死锁处理策略：
1. 死锁检测 (Deadlock Detection)：允许死锁发生，但能检测并解决。
  - 超时 (Timeout)：如果事务等待超过指定时间，则假定发生死锁并中止该事务。
  - 等待图 (Wait-for Graph)：
    - $G = <V, E>$ ，其中 $V$ 是事务集合， $E$ 是等待关系（ $<T_i, T_j>$ 表示 $T_i$ 等待 $T_j$ ）。
    - 判断：如果图中存在环，则发生死锁。
    - 检测时机：
      1. 每当一个事务等待时。
      2. 周期性检测。
    - 检测到死锁后的处理：
      1. 选择一个牺牲者 (victim)（如最年轻的事务、中止成本最小的事务）。
      2. 中止牺牲者，释放其锁和资源。
      3. 授予等待者资源。
      4. 重启牺牲者（自动或手动）。
2. 死锁避免 (Deadlock Avoidance)：预防死锁发生。
  - 一次性请求所有锁 (Requesting all locks at initial time of transaction)：
    - 原理：事务在开始执行前，一次性声明并请求所有它可能需要的锁。如果所有锁都能被授予，事务才开始执行；否则，事务等待直到所有锁都被授予。
    - 优点：简单，可以完全避免死锁。
    - 缺点：
      - 降低并发度：事务可能长时间持有不必要的锁，限制了其他事务的并发执行。
      - 难以实现：在事务开始前，很难准确预知所有需要访问的数据对象。
      - 资源利用率低：可能导致资源浪费。
  - 按指定顺序请求锁 (Requesting locks in a specified order of resource)：
    - 原理：对所有资源（数据项）进行全局排序，所有事务都必须按照这个预定义的顺序来请求锁。
    - 优点：可以避免死锁，因为循环等待不可能发生（如果所有事务都遵循相同的偏序）。
    - 缺点：
      - 实现复杂：需要对所有数据项进行全局排序，并强制所有事务遵循此顺序。
      - 灵活性差：事务可能需要访问的数据项顺序与预定义顺序不符，导致不必要的等待或锁请求。
      - 降低并发度：事务可能需要请求并持有它暂时不需要的锁，只为了遵循顺序。
  - 冲突时中止 (Abort once conflicted)：
    - 原理：当一个事务请求一个已被其他事务持有的锁时，如果发生冲突，请求方事务立即中止并回滚。
    - 优点：简单，无需复杂的死锁检测或避免机制。
    - 缺点：
      - 频繁中止：在高并发环境下可能导致大量事务被中止和重启，降低系统吞吐量。
      - 饥饿 (Starvation)：某些事务可能因为频繁被中止而永远无法完成。
  - 事务重试 (Transaction Retry)：
    - 原理：为每个事务分配一个唯一的时间戳 (Time Stamp)。当一个事务 $T_A$ 请求一个已被 $T_B$ 持有的锁时，根据时间戳比较来决定是等待还是中止。
    - 核心思想：通过强制单向等待来打破循环等待条件，从而避免死锁。
    - 两种主要策略：
      - Wait-die (等待-死亡)：
        
        规则：如果 $T_A$ （请求者）比 $T_B$ （持有者）老（时间戳小），则 $T_A$ 等待。否则（ $T_A$ 比 $T_B$ 年轻）， $T_A$ “死亡”，即它被中止并以原始时间戳自动重试。
        
        特点：老事务等待年轻事务，年轻事务死亡。这确保了老事务最终会完成，避免了饥饿。
        
        示例：
        
        $T_A$ （时间戳=10）请求 $R_1$ ，被 $T_B$ （时间戳=20）持有。 $T_A$ 比 $T_B$ 老，所以 $T_A$ 等待。
        
        $T_C$ （时间戳=30）请求 $R_2$ ，被 $T_D$ （时间戳=20）持有。 $T_C$ 比 $T_D$ 年轻，所以 $T_C$ 死亡并重试。
      - Wound-wait (伤害-等待)：
        
        规则：如果 $T_A$ （请求者）比 $T_B$ （持有者）年轻（时间戳大），则 $T_A$ 等待。否则（ $T_A$ 比 $T_B$ 老）， $T_A$ “伤害” $T_B$ ，即 $T_B$ 被中止并以原始时间戳自动重试。
        
        特点：年轻事务等待老事务，老事务伤害年轻事务。这确保了老事务可以抢占资源，避免了饥饿。
        
        示例：
        
        $T_A$ （时间戳=10）请求 $R_1$ ，被 $T_B$ （时间戳=20）持有。 $T_A$ 比 $T_B$ 老，所以 $T_A$ 伤害 $T_B$ （ $T_B$ 被中止并重试）。
        
        $T_C$ （时间戳=30）请求 $R_2$ ，被 $T_D$ （时间戳=20）持有。 $T_C$ 比 $T_D$ 年轻，所以 $T_C$ 等待。
    - 共同优点：
      - 避免死锁：由于强制了单向等待（要么老等年轻，要么年轻等老），不可能出现循环等待。
      - 避免饥饿：通过时间戳机制，确保了事务最终能够完成。
    - 区别对比：
      - Wait-die：老事务等待，年轻事务回滚。倾向于让老事务先完成。
      - Wound-wait：年轻事务等待，老事务回滚年轻事务。倾向于让老事务先完成。
      - 两者在事务中止的时机和被中止的事务类型上有所不同，但都有效避免了死锁。

总结：

本笔记详细阐述了数据库管理系统的核心原理，包括其架构、数据访问管理、查询优化、恢复机制和并发控制。

DBMS架构：理解单进程、多进程、多线程结构的优缺点及适用场景，是理解现代数据库系统运行方式的基础。
数据访问管理：文件组织和索引技术是影响数据库性能的关键。B+树作为最常用的索引结构，其原理和应用需要重点掌握。
查询优化：分为代数优化和操作优化。代数优化通过关系代数等价变换来重写查询，核心是下推选择和投影以减少中间结果集。操作优化则选择具体的算法和访问路径，连接操作的优化是难点和重点。
恢复：事务的ACID特性是数据库可靠性的基石。理解日志先行规则和提交规则，以及不同更新策略下的Undo/Redo机制，是掌握数据库恢复原理的关键。
并发控制：理解并发带来的数据不一致问题（丢失更新、脏读、不可重复读）及其根源。可串行化是并发控制的正确性准则。两阶段封锁协议（2PL）是实现可串行化的重要方法，其不同变种（S/X锁、S/U/X锁）在并发度和开销之间进行权衡。死锁是并发控制中的常见问题，需要掌握死锁检测（等待图）和死锁避免（时间戳排序算法如Wait-die和Wound-wait）的原理和方法。

考试复习重点：

DBMS核心组件及其功能（特别是查询处理流程）。
多线程结构作为现代DBMS主流进程结构的特点。
B+树索引的工作原理和优势。
查询优化中的代数优化原则（下推选择/投影）和关系代数等价变换规则。
连接操作的各种算法（嵌套循环、归并排序、哈希连接）及其成本分析。
事务的ACID特性及其重要性。
日志先行规则和提交规则的含义和作用。
Undo/Redo机制在不同更新策略下的应用。
并发控制中的常见问题（丢失更新、脏读、不可重复读）及其产生原因。
可串行化的概念。
**两阶段封锁协议（2PL）**的定义、阶段划分及其保证可串行化的原理。
死锁的定义，以及**死锁检测（等待图）和死锁避免（Wait-die, Wound-wait）**的原理和区别。

易混淆或常考知识点对比强调：

进程与线程在DBMS结构中的应用和优缺点对比。
代数优化与操作优化的区别和联系。
Wait-die与Wound-wait两种死锁避免策略的详细规则和效果对比。
S锁、X锁、U锁的兼容性矩阵和应用场景。
聚簇索引与非聚簇索引的物理存储和查询效率差异。

1. 数据库管理系统（DBMS）架构​

1.1 DBMS核心组件 (The Components of DBMS Core)​

1.2 DBMS进程结构 (The Process Structure of DBMS)​

2. 数据库访问管理 (Database Access Management)​

2.1 访问类型 (Access Types)​

2.2 文件组织 (File Organization)​

2.3 索引技术 (Index Technique)​

3. 查询优化 (Query Optimization)​

3.1 查询优化概述 (Summary of Query Optimization)​

3.2 查询的等价转换 (The Equivalent Transform of a Query)​

3.3 操作优化 (The Operation Optimization)​

4. 恢复 (Recovery)​

4.1 恢复简介 (Introduction)​

4.2 事务 (Transaction)​

4.3 支持恢复的结构 (Some Structures to Support Recovery)​

4.4 提交规则和日志先行规则 (Commit Rule and Log Ahead Rule)​

5. 并发控制 (Concurrency Control)​

5.1 并发控制简介 (Introduction)​

5.2 可串行化 (Serialization)​

5.3 封锁协议 (Locking Protocol)​

5.4 死锁与活锁 (Deadlock & Live Lock)​